package mycollections.list;

import mycollections.MyConcurrentModificationException;

import java.util.Collection;
import java.util.Iterator;

public class MyLinkedList<E> implements MyList<E>, MyStack<E>, MyQueue<E> {
    Node<E> first, last;
    private int size;
    private int modificationCount;

    static class Node<E> {
        E item;
        Node<E> prev, next;

        private Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }

        private Node(E item) {
            this.item = item;
        }

        private Node(Node<E> prev, E item) {
            this.item = item;
            this.prev = prev;
        }

        private Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    class MyIterator implements Iterator<E> {
        Node<E> current;
        private int expectedModificationCount;
        private boolean descending;

        private MyIterator() {
            this(false);
        }

        private MyIterator(boolean descending) {
            this.descending = descending;
            if (descending) {
                this.current = MyLinkedList.this.last;
            } else {
                this.current = MyLinkedList.this.first;
            }
            this.expectedModificationCount = modificationCount;
        }

        private void checkComodification() {
            if (expectedModificationCount != modificationCount)
                throw new MyConcurrentModificationException();
        }

        @Override
        public boolean hasNext() {
            checkComodification();
            return descending ? current != null : current != null;
        }

        @Override
        public E next() {
            checkComodification();
            E item = current.item;
            current = descending ? current.prev : current.next;
            return item;
        }

        @Override
        public void remove() {
            checkComodification();
            Node prev = current;
            current = current.next;
            MyLinkedList.this.remove(prev);
            expectedModificationCount = modificationCount;
        }

        @Override
        public int hashCode() {
            return current.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof MyLinkedList.MyIterator))
                return false;
            else {
                MyIterator other = (MyIterator) obj;
                return current == other.current;
            }
        }
    }

    public MyLinkedList() {

    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size)
            throw new MyIndexOutOfBoundsException(index);
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index > size)
            throw new MyIndexOutOfBoundsException(index);
    }

    private Node<E> getNode(int index) {
        Node<E> curr;
        if (index < size >> 1) {
            curr = first;
            while (index-- != 0) {
                curr = curr.next;
            }
        } else {
            curr = last;
            while (index++ < size - 1) {
                curr = curr.prev;
            }
        }
        return curr;
    }

    private void addFirst(E e) {
        first.prev = new Node<>(e, first);
        first = first.prev;
        size++;
        modificationCount++;
    }

    private void addBefore(E e, Node<E> node) {
        Node prev = node.prev;
        node.prev = new Node<>(prev, e, node);
        if (node.prev.prev != null)
            node.prev.prev.next = node.prev;
        if (prev == null)
            first = node.prev;
        size++;
        modificationCount++;
    }

    private void addLast(E e) {
        if (isEmpty()) {
            first = last = new Node<>(e);
        } else {
            last.next = new Node<>(last, e);
            last = last.next;
        }
        size++;
        modificationCount++;
    }

    private E removeFirst() {
        E item = first.item;
        if (size==1)
            clear();
        else {
            first = first.next;
            first.prev = null;
            size--;
            modificationCount++;
        }

        return item;
    }

    private E remove(Node<E> node) {
        E item = node.item;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        modificationCount++;
        return item;
    }

    private E removeLast() {
        E item = last.item;
        last = last.prev;
        last.next = null;
        size--;
        modificationCount++;
        return item;
    }


    @Override
    public void add(E e) {
        addLast(e);
    }

    @Override
    public void add(int index, E e) {
        checkPositionIndex(index);
        if (index == size)
            addLast(e);
        else if (index == 0)
            addFirst(e);
        else
            addBefore(e, getNode(index));
    }

    @Override
    public void addAll(Collection<? extends E> c) {
        addAll(size, c);
    }

    @Override
    public void addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
        if (c.isEmpty())
            return;
        Node<E> subFirst, subLast;
        Iterator<? extends E> i = c.iterator();
        subFirst = subLast = new Node<>(i.next());
        while (i.hasNext()) {
            subLast = subLast.next = new Node<>(subLast, i.next());
        }
        if (isEmpty()) {
            first=subFirst;
            last=subLast;
        } else {
            if (index == size) {
                subFirst.prev = last;
                last.next = subFirst;
                last = subLast;
            } else if (index == 0) {
                first.prev = subLast;
                subLast.next = first;
                first = subFirst;
            } else {
                Node<E> node = getNode(index);
                node.prev.next = subFirst;
                subFirst.prev = node.prev;
                subLast.next = node;
                node.prev = subLast;
            }
        }
        size += c.size();
        modificationCount += c.size();
    }

    @Override
    public E get(int index) {
        checkElementIndex(index);
        return getNode(index).item;
    }

    @Override
    public E remove(int index) {
        checkElementIndex(index);
        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            return remove(getNode(index));
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = last = null;
        modificationCount = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void set(int index, E e) {
        checkElementIndex(index);
        getNode(index).item = e;
        modificationCount++;
    }

    @Override
    public int indexOf(E e) {
        Node current = first;
        int index = 0;
        while (index < size && !current.item.equals(e)) {
            current = current.next;
            index++;
        }
        return index == size ? -1 : index;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        Object a[] = new Object[size];
        Node curr = first;
        for (int i = 0; i < size; i++, curr = curr.next) {
            a[i] = curr.item;
        }
        return a;
    }

    @Override
    public Iterator<E> iterator() {
        return new MyIterator();
    }

    public Iterator<E> descendingIterator() {
        return new MyIterator(true);
    }

    @Override
    public void offer(E e) {
        add(e);
    }

    @Override
    public E peek() {
        if (!isEmpty())
            return first.item;
        else throw new MyNoSuchElementException();
    }

    @Override
    public E poll() {
        if (!isEmpty())
            return removeFirst();
        else throw new MyNoSuchElementException();
    }

    @Override
    public void push(E e) {
        add(e);
    }

    @Override
    public E pop() {
        if (!isEmpty())
            return removeLast();
        else throw new MyNoSuchElementException();
    }
}